package 剑指II;

import 我的JDK基础数据结构.HashMap.HashMap;

import java.util.Map;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-11-04
 **/

public class Jz017含有所有字符的最短字符串 {

    /**
     * 给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。
     * 如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
     * 如果 s 中存在多个符合条件的子字符串，返回任意一个。
     * 注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
     * <p>
     * 示例 1：
     * 输入：s = "ADOBECODEBANC", t = "ABC"
     * 输出："BANC"
     * 解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'
     * 示例 2：
     * 输入：s = "a", t = "a"
     * 输出："a"
     * 示例 3：
     * 输入：s = "a", t = "aa"
     * 输出：""
     * 解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。
     *  
     * 提示：
     * 1 <= s.length, t.length <= 105
     * s 和 t 由英文字母组成
     * <p>
     * 进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
     */


    public String minWindow(String s, String t) {
        Map<Character, Integer> map = new HashMap<>();
        char[] bigArr = s.toCharArray();
        char[] smallArr = t.toCharArray();
        int count = 0;
        for (char c : smallArr) {
            Integer put = map.put(c, map.getOrDefault(c, 0) + 1);
            if (put == null) {
                count++;
            }
        }
        int left = 0;
        int right = 0;
        int minLength = Integer.MAX_VALUE;
        Integer resultLeft = null;
        int resultRight = 0;

        while (right < bigArr.length) {

            char c = bigArr[right];

            if (map.containsKey(c)) {
                Integer oldValue = map.put(c, map.get(c) - 1);
                if (oldValue == 1) {
                    count--;
                }
            }

            // count为0了就收缩左指针
            while (count == 0 && left < right) {
                char lC = bigArr[left++];
                if (map.containsKey(lC)) {
                    // 不能加了,加了就吃不完了
                    if (map.get(lC) == 0) {
                        left--;
                        break;
                    }
                    map.put(lC, map.get(lC) + 1);
                }
            }

            if (count == 0 && right - left < minLength) {
                resultLeft = left;
                resultRight = right;
                minLength = right - left;
            }

            right++;

        }

        if (resultLeft == null) {
            return "";
        }

        return s.substring(resultLeft, resultRight + 1);
    }

    public static void main(String[] args) {
        Jz017含有所有字符的最短字符串 n = new Jz017含有所有字符的最短字符串();
        String result = n.minWindow("ab", "a");
        System.out.println(result);
    }

}
